package com.lili.divide;

/**
 * @Auther: 李 力
 * @Date: 2024/8/20
 * @Description: 快速幂问题
 * @version: 1.0
 */
public class QuickPower {
    public static double quickPower(double x, int n) {
        if (n == 1) {
            return x;
        }
        if (n % 2 == 0) {
            //偶数
            return quickPower(x, n / 2) * quickPower(x, n / 2);
        } else {
            //基数
            return quickPower(x, n / 2) * quickPower(x, n / 2) * x;
        }
    }

    //优化如下:
    public static double quickPower2(double x, int n) {
        if (n == 1) {
            return x;
        }
        double r = quickPower2(x, n / 2);
        if (n % 2 == 0) {
            //偶数
            return r * r;
        } else {
            //基数
            return r * r * x;
        }
    }

    //考虑n为0的情况
    public static double quickPower3(double x, int n) {
        if (n == 0) {
            return 1.0;
        }
        if (n == 1) {
            return x;
        }
        double r = quickPower3(x, n / 2);
        if (n % 2 == 0) {
            return r * r;
        } else {
            return r * r * x;
        }
    }

    //再次考虑n为负数的情况
    public static double myPow(double x, int n) {
        int p = n;
        if (p < 0) {
            p = -p;
        }
        double r = quickPower3(x, p);
        return n < 0 ? 1 / r : r;
    }
}
